<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>最小堆排序拖动示例</title>
    <script src="https://d3js.org/d3.v7.min.js"></script>
    <style>
        .element {
            fill: steelblue;
            stroke: black;
            stroke-width: 2;
        }

        .sorted-element {
            fill: red;
            stroke: black;
            stroke-width: 2;
        }

        .box {
            fill: lightgrey;
            stroke: black;
            stroke-width: 2;
        }

        .label {
            text-anchor: middle;
            fill: white;
        }

        .output, .correct-sequence, .record {
            font-size: 14px;
            margin-top: 20px;
        }

        .button {
            margin-top: 20px;
        }

        .container {
            display: flex;
        }

        .linear-list, .binary-tree {
            margin: 20px;
        }
    </style>
</head>
<body>
<div class="success-message" style="color: red; font-size: 100px; display: none;"></div>
<div class="container">
    <div class="linear-list">
        <h2>线性表</h2>
        <svg id="linear-list" width="600" height="300"></svg>
        <button class="button" id="finish">结束拖动</button>
    </div>
    <div class="binary-tree">
        <h2>二叉树</h2>
        <svg id="binary-tree" width="600" height="400"></svg>
    </div>
</div>
<div class="output"></div>
<div class="correct-sequence"></div>
<div class="record"></div>

<script>
    const data = Array.from(new Set(Array.from({length: 5}, () => Math.floor(Math.random() * 10) + 1)));
    const svg = d3.select("#linear-list");
    const binarySvg = d3.select("#binary-tree");
    const radius = 20;
    const boxes = Array(data.length).fill(null);
    const correctSequence = getMinHeapSortSteps();
    let currentStep = 0;

    // 创建空的框
    for (let i = 0; i < data.length; i++) {
        svg.append("rect")
            .attr("class", "box")
            .attr("x", (i + 1) * 100 - 30)
            .attr("y", 200)
            .attr("width", 60)
            .attr("height", 60)
            .attr("fill", "lightgrey");
    }

    // 创建元素并绑定拖动事件
    const elements = svg.selectAll("g")
        .data(data)
        .enter().append("g")
        .attr("transform", (d, i) => `translate(${(i + 1) * 100}, 230)`)
        .call(d3.drag()
            .on("start", dragstarted)
            .on("drag", dragged)
            .on("end", dragended));

    data.forEach((value, index) => {
        boxes[index] = value;
    });
    displayBinaryTree(boxes.filter(val => val !== null));

    elements.append("circle")
        .attr("class", "element")
        .attr("r", radius);

    elements.append("text")
        .attr("class", "label")
        .attr("y", 5)
        .text(d => d);

    // 显示正确的排序步骤
    const correctSequenceDiv = document.querySelector(".correct-sequence");
    correctSequenceDiv.innerHTML = `每一步的正确排序状态: <br>${correctSequence.join("<br>")}`;

    // 点击结束按钮时执行的动作
    document.getElementById("finish").addEventListener("click", finishDragging);

    function dragstarted(event) {
        d3.select(this).raise().attr("fill", "orange");
    }

    function dragged(event) {
        d3.select(this).attr("transform", `translate(${event.x}, ${event.y})`);
    }

    function dragended(event, d) {
        const elementGroup = d3.select(this);
        const x = event.x;
        const y = event.y;
        let isInBox = false;

        // 检查元素是否放入框内
        for (let i = 0; i < boxes.length; i++) {
            const boxX = (i + 1) * 100 - 30;
            const boxY = 200;
            const boxWidth = 60;
            const boxHeight = 60;

            if (x >= boxX && x <= boxX + boxWidth && y >= boxY && y <= boxY + boxHeight) {
                isInBox = true;

                boxes[i] = d;
                elementGroup.transition()
                    .duration(500)
                    .attr("transform", `translate(${(i + 1) * 100}, 230)`);

                // 更新二叉树
                displayBinaryTree(boxes.filter(val => val !== null));
                if(currentStep>0){
                    highlightBinaryTreeNodes(currentStep-1)
                }
                return;
            }
        }
    }

    function finishDragging() {
        const currentSequence = boxes.map((d, i) => d !== null ? d : data[i]);
        const correctStep = correctSequence[currentStep];

        if (JSON.stringify(currentSequence) === JSON.stringify(correctStep)) {
            alert("这一步正确！");
            swapHeapTopWithEnd(currentStep);
            highlightHeapTop(currentStep);
            currentStep++;

            if (currentStep >= correctSequence.length) {
                alert("成功结束，恭喜！");
                document.querySelector(".success-message").style.display = "block";
                document.querySelector(".success-message").innerText = "成功人士！";
            }

        } else {
            alert("这一步错误，请再试一次！");
        }
    }

    function getMinHeapSortSteps() {
        const sortSteps = [];
        const copyData = [...data];

        for (let i = Math.floor(copyData.length / 2) - 1; i >= 0; i--) {
            minHeapify(copyData, copyData.length, i);
        }
        sortSteps.push([...copyData]);

        for (let i = copyData.length - 1; i > 0; i--) {
            [copyData[0], copyData[i]] = [copyData[i], copyData[0]];
            minHeapify(copyData, i, 0);
            sortSteps.push([...copyData]);
        }

        return sortSteps;
    }

    function minHeapify(arr, length, i) {
        let smallest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;

        if (left < length && arr[left] < arr[smallest]) {
            smallest = left;
        }
        if (right < length && arr[right] < arr[smallest]) {
            smallest = right;
        }
        if (smallest !== i) {
            [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
            minHeapify(arr, length, smallest);
        }
    }

    function highlightHeapTop(step) {
        const heapTop = correctSequence[step][0];
        svg.selectAll("g").each(function (d) {
            if (d === heapTop) {
                d3.select(this).select("circle").attr("class", "sorted-element");
            }
        });
    }

    function highlightBinaryTreeNodes(step) {
        for (let i = 0; i <= step; i++) {
            const heapTop = correctSequence[i][0];
            // 高亮堆顶和尾节点
            binarySvg.selectAll("circle").each(function (d) {
                console.log("检查节点:", d, " heapTop:", heapTop);
                if (String(d) === String(heapTop)) {  // 确保数据类型一致
                    d3.select(this).attr("class", "sorted-element");
                }
            });
        }
    }

    function swapHeapTopWithEnd(step) {
        const endIndex = correctSequence[step].length - 1 - step;
        const heapTop = correctSequence[step][0];
        const endElement = correctSequence[step][endIndex];

        const topElementGroup = svg.selectAll("g").filter(d => d === heapTop);
        const endElementGroup = svg.selectAll("g").filter(d => d === endElement);

        const topTransform = topElementGroup.attr("transform");
        const endTransform = endElementGroup.attr("transform");

        topElementGroup.transition().duration(500).attr("transform", endTransform);
        endElementGroup.transition().duration(500).attr("transform", topTransform);
        [boxes[0], boxes[endIndex]] = [boxes[endIndex], boxes[0]];
        displayBinaryTree(boxes.filter(val => val !== null), step);
        highlightBinaryTreeNodes(step);
    }

    function displayBinaryTree(arr) {
        binarySvg.selectAll("*").remove();

        const radius = 20;
        const nodeSpacingX = 100;
        const nodeSpacingY = 60;

        function drawNode(value, x, y, depth) {
            if (value == null) return;

            // 为每个circle绑定数据
            const node = binarySvg.append("circle")
                .attr("cx", x)
                .attr("cy", y)
                .attr("r", radius)
                .attr("class", "element")
                .data([value]); // 绑定数据

            binarySvg.append("text")
                .attr("x", x)
                .attr("y", y + 5)
                .attr("class", "label")
                .text(value);

            const leftIndex = 2 * depth + 1;
            const rightIndex = 2 * depth + 2;

            if (leftIndex < arr.length && arr[leftIndex] != null) {
                binarySvg.append("line")
                    .attr("x1", x)
                    .attr("y1", y + radius)
                    .attr("x2", x - nodeSpacingX / (depth + 1))
                    .attr("y2", y + nodeSpacingY - radius)
                    .attr("stroke", "black");

                drawNode(arr[leftIndex], x - nodeSpacingX / (depth + 1), y + nodeSpacingY, leftIndex);
            }

            if (rightIndex < arr.length && arr[rightIndex] != null) {
                binarySvg.append("line")
                    .attr("x1", x)
                    .attr("y1", y + radius)
                    .attr("x2", x + nodeSpacingX / (depth + 1))
                    .attr("y2", y + nodeSpacingY - radius)
                    .attr("stroke", "black");

                drawNode(arr[rightIndex], x + nodeSpacingX / (depth + 1), y + nodeSpacingY, rightIndex);
            }
        }

        // 每次拖动后都实时绘制新的二叉树结构
        drawNode(arr[0], 300, 50, 0);
    }
</script>
</body>
</html>
